Store-and-forward devices, such as switches and routers, are used in packet networks, such as the Internet, for directing traffic at interconnection points. The store-and-forward devices include a plurality of line cards for receiving and transmitting data from/to external sources. The line cards are connected to one another via a backplane and a switching fabric. The backplane provides data paths between line cards and the switching fabric and the switching fabric provides configurable data paths between line cards. The line cards receiving data from external sources (ingress ports) receive data (packets) of various sizes. The data received are stored in queues prior to being transmitted to the appropriate line cards for transmission to external sources (egress ports). The packets include a header that identifies the destination of the packet. The packet is stored in the queue associated with that destination. The packet may also identify a priority for the data and the ingress port may also include queues for the various priorities.
The ingress ports send requests for transmitting data to a scheduler within the switching fabric. The scheduler generates grants for the queues that should transmit packets therefrom. The packets are switched through a crossbar switching matrix in batches. A batch consists of at most one packet selected from each input port. Thus, no more than one of the packets is destined for each output port. The packets in a batch are transferred in parallel across the crossbar switching matrix. While the packets from a scheduled batch are being transferred through the crossbar, the scheduler can select the packets to form the next batch, so that the transmission of the new batch of packets can start as soon as transmission of the current batch ends. At the end of the batch of packets, the fabric scheduler re-configures the crossbar switching matrix so as to connect the input ports to the corresponding output ports where the next packet is destined to.
Because the packets are transferred in batches, the switching paths in the crossbar switching matrix are kept unchanged for the duration of the longest packet being transferred across the crossbar in that batch. When the packets are of variable size (as is the case for packets generated by most network protocols in the industry), this results in wasted bandwidth. For example, when a 50-byte packet and a 1500-byte packet are part of the same batch, the crossbar is maintained in the same configuration for the duration of the 1500-byte packet, and only 1/30th of the bandwidth of the path is used by the 50-byte packet.
One solution for avoiding the inefficiency caused by variable-size packets is to divide the packets into fixed-size units before switching through the crossbar switching fabric, and combine the fragments into the original packet at the output of the fabric. The packet fragments switched through the crossbar are called “segments” or “cells”. The fabric scheduler selects at most one cell from each input port to form a batch, such that the destination port numbers associated with the cells in the same batch are distinct. The cells in the same batch are then transmitted in parallel. Because the cells are of the same size, no bandwidth is wasted in the crossbar. The cells switched through the fabric have a fixed size. This fixed size is typically chosen to correspond to the size of the smallest packet switched by the fabric, plus the size of any internal headers added by the router or switch before passing the packet through the fabric.
The fabric scheduler computes a new schedule for the batch of cells during the transmission time of a cell. In a high-speed switch, this time interval can be extremely short. For example, with a cell size of 64 bytes and a port rate of 10 Gigabits/second, the fabric scheduler schedules a new batch of cells every 51.2 nanoseconds. The crossbar switching matrix is also configured at intervals of 51.2 nanoseconds. As the port speed is increased, both the fabric scheduler and the crossbar reconfiguration are made correspondingly faster. This is especially a problem when an optical switching device is used as the crossbar switching matrix. While supporting very high data rates, many of the optical switching devices have long reconfiguration times. This makes them unsuitable for use in a cell-based fabric.
Another difficulty with the cell-based fabric is that it is difficult to separate the crossbar switching matrix (the data path) and the fabric scheduler, because the delays in communication between them can become a bottleneck. During every scheduling cycle, the header information (in particular, the destination port number) from cells stored in the input buffers of the crossbar matrix is passed to the fabric scheduler, and the crossbar configuration setting is communicated back from the scheduler to the crossbar matrix. If the scheduler is physically separated from the crossbar matrix (on separate chips or circuit boards), the delays in communication between the two may make it difficult to achieve the scheduling rate needed in a high-speed router or switch.